#include "classical-problems.h"
#include <algorithm>
#include <string.h>
#include <time.h>

namespace pot {
void ShellShift(int A[], int n, int i) {  
  int N = 0;
  // here can use N == n, or s == m as exit condition
  //int m = gcd(n, i);
  for (int s = 0; ; ++s) {
    int k = s;
    int tmp = A[k];
    while (true) {
      ++N;
      int j = (k + i) % n;

      if (j == s) {
        A[k] = tmp;
        break;
      }

      A[k] = A[j];
      k = j;
    }
    if (n == N) break;
  }
  //printf("Shell Shift: N = %d, n = %d\n", N, n);
}

int N = 0;
void IncrementalShift(int A[], int n, int i) {
  if (i == 0 || i == n) return;

  int m = n - i;
  if (i < m) {
    for (int j = 0; j < i; ++j) {
      std::swap(A[j], A[m + j]);
      //++N;
    }
    IncrementalShift(A, m, i);
  }
  else {
    for (int j = 0; j < m; ++j) {
      std::swap(A[j], A[i + j]);
      //++N;
    }
    IncrementalShift(A + m, i, i - m);
  }  
}

void IncrementalShiftTest(int A[], int n, int i) {
  //N = 0;
  IncrementalShift(A, n, i);
  //printf("Incremental Shift: N = %d\n", N);
}

void Reverse(int A[], int s, int e) {
  while (s < --e) {
    std::swap(A[s], A[e]);
    ++s;    
    //++N;
  }
}

void Shift(int A[], int n, int i) {
  //N = 0;
  Reverse(A, 0, i);
  Reverse(A, i, n);
  Reverse(A, 0, n);
  //printf("Shift: N = %d\n", N);
}

void Check(int O[], int A[], int n, int i, const char *msg) {
  int m = n - i;
  for (int j = 0; j < m; ++j) {
    if (A[j] != O[i + j]) {
      printf("error:%s\n", msg);
      return;
    }
  }
  for (int j = 0; j < i; ++j) {
    if (O[j] != A[m + j]) {
      printf("error:%s\n", msg);
      return;
    }
  }
}

void Check(int A[], int B[], int n) {
  for (int i = 0; i < n; ++i) {
    if (A[i] != B[i]) {
      printf("%d, %d\n", i, A[i]);
    }
  }
}

static const char *MethodNames[] = {
  "Incremental Shift",
  "Shift",  
  "Shell Shift"
};

typedef void (*ShiftFunc)(int *, int n, int i);

static ShiftFunc ShiftFuncs[] = {
  IncrementalShift,
  Shift,  
  ShellShift
};


void ShiftVectorTest(int n) {  
  int *O = new int[n];
  int *A[3];  

  GenSignedIntegers(O, n);
  for (int j = 0; j < 3; ++j) {
    A[j] = new int[n];
    memcpy(A[j], O, sizeof(int) * n);
  }

  int offset = rand() % (n / 4);
  int i = n / 2 + ((rand() % 2) == 0 ? -offset : offset);

  clock_t t[4];
  for (int j = 0; j < 3; ++j) {
    t[j] = clock();
    ShiftFuncs[j](A[j], n, i);
  }
  t[3] = clock();

  for (int j = 0; j < 3; ++j) {
    Check(O, A[j], n, i, MethodNames[j]);
  }
  float elapsed[3];
  for (int j = 0; j < 3; ++j) {
    elapsed[j] = (t[j + 1] - t[j]) / 1000.0;
  }  
  int asd[3];
  for (int j = 0; j < 3; ++j) asd[j] = j;
  
  for (int j = 2; j > 0; --j) {
    for (int k = 0; k < j; ++k) {
      if (elapsed[k] > elapsed[k + 1]) {
        std::swap(elapsed[k], elapsed[k + 1]);
        std::swap(asd[k], asd[k + 1]);
      }
    }
  }

  for (int j = 0; j < 3; ++j) {
    printf("%s: %f\n", MethodNames[asd[j]], elapsed[j]);
  }

  delete[] O;
  for (int j = 0; j < 3; ++j) delete[] A[j];

  printf("\n*************************************\n");
}

void ShiftVectorTest() {
  int n = 100000000;
  int m = n / 10;
  for (int i = 0; i < 10; ++i) {
    ShiftVectorTest(i * m + rand() % m);
  }
}
} // pot
